#include "FibonacciHeap.h"

template<class Key>
PriorityQueue<Key>::~PriorityQueue() {
	if (headVertex_) {
		REQURSIVE_DELETE(headVertex_);
	}
}

template<class Key>
typename PriorityQueue<Key>::Vertex*
PriorityQueue<Key>::insert(Vertex* newVertex) {
	if (!newVertex) {
		return newVertex;
	}
	++numberOfVertex_;
	if (!headVertex_) {
		headVertex_ = newVertex;
		return newVertex;
	}
	headVertex_->next->prev = newVertex;
	newVertex->next = headVertex_->next;
	newVertex->prev = headVertex_;
	headVertex_->next = newVertex;
	if (newVertex->key > headVertex_->key) {
		headVertex_ = newVertex;
	}
	return newVertex;
}

template<class Key>
typename PriorityQueue<Key>::Vertex*
PriorityQueue<Key>::insert(Key newKey) {
	Vertex* newVertex = new Vertex(newKey);
	newVertex->next = newVertex;
	newVertex->prev = newVertex;
	return this->insert(newVertex);
}


template<class Key>
typename PriorityQueue<Key>::Vertex*
PriorityQueue<Key>::getMax() {
	return headVertex_;
}


template<class Key>
typename PriorityQueue<Key>::Vertex*
PriorityQueue<Key>::extractMax() {
	Vertex* oldMax = headVertex_;
	if (!oldMax) {
		return oldMax;
	}
	Vertex* child = oldMax->child;
	int counter = 0;
	int numberOfChildren = oldMax->numberOfChildren;
	while (counter < numberOfChildren) {
		child->parent = nullptr;
		Vertex* nextChild = child->next;
		this->insert(child);
		child = nextChild;
		++counter;
	}
	oldMax->prev->next = oldMax->next;
	oldMax->next->prev = oldMax->prev;
	--numberOfVertex_;
	if (oldMax == oldMax->next) {
		headVertex_ = nullptr;
	}
	else {
		headVertex_ = oldMax->next;
		CONSOLIDATE();
	}
	return oldMax;
}


template<class Key>
bool
PriorityQueue<Key>::increaseKey(Vertex* currentVertex, Key newKey) {
	if (!currentVertex)
		return false;
	if (currentVertex->key > newKey)
		return false;

	currentVertex->key = newKey;
	Vertex* parent;
	if ((parent = currentVertex->parent) && currentVertex->key > parent->key) {
		CUT(currentVertex, parent);
		CASCADING_CUT(parent);
	}
	if (currentVertex->key > headVertex_->key) {
		headVertex_ = currentVertex;
	}
	return true;
}


template<class Key>
void
PriorityQueue<Key>::REQURSIVE_DELETE(Vertex* x) {
	if (x->child) {
		REQURSIVE_DELETE(x->child);
	}
	if (x->next != x) {
		Vertex* next = x->next;
		if (next && x->prev) {
			x->next->prev = nullptr;
			x->prev->next = nullptr;
		}
		delete x;
		if (next)
			REQURSIVE_DELETE(next);
	}
	else {
		delete x;
	}
}


template<class Key>
void
PriorityQueue<Key>::FIB_LINK(Vertex* y, Vertex* x) {
	if (x == y) {
		return;
	}
	y->prev->next = y->next;
	y->next->prev = y->prev;
	--numberOfVertex_;
	if (x->numberOfChildren) {
		x->child->next->prev = y;
		y->next = x->child->next;
		x->child->next = y;
		y->prev = x->child;
	}
	else {
		y->next = y;
		y->prev = y;
	}
	y->parent = x;
	x->child = y;
	++x->numberOfChildren;
}

template<class Key>
void
PriorityQueue<Key>::CONSOLIDATE() {
	vector<Vertex*> uniqueTree(numberOfVertex_, nullptr);
	Vertex* processVertex = headVertex_;
	int startNumberOfVertex = numberOfVertex_;
	for (int i = 0; i < startNumberOfVertex; ++i) {
		int index = processVertex->numberOfChildren;
		Vertex* x = processVertex;
		while (uniqueTree[index]) {
			Vertex* y = uniqueTree[index];
			if (y->key > x->key) {
				Vertex* tmp = x;
				x = y;
				y = tmp;
			}
			FIB_LINK(y, x);
			uniqueTree[index] = nullptr;
			++index;
		}
		uniqueTree[index] = x;
		processVertex = processVertex->next;
	}
	headVertex_ = nullptr;
	numberOfVertex_ = 0;
	for (int i = 0; i < startNumberOfVertex; ++i) {
		if (uniqueTree[i] != nullptr) {
			uniqueTree[i]->next = uniqueTree[i];
			uniqueTree[i]->prev = uniqueTree[i];
			this->insert(uniqueTree[i]);
		}
	}
}

template<class Key>
void
PriorityQueue<Key>::CUT(Vertex* x, Vertex* y) {
	Vertex* childVertex = y->child;
	while (childVertex != x) {
		childVertex = childVertex->next;
	}
	childVertex->prev->next = childVertex->next;
	childVertex->next->prev = childVertex->prev;
	if (childVertex == y->child) {
		y->child = childVertex->next;
	}
	x = insert(x);
	x->parent = nullptr;
	x->mark = false;
}

template<class Key>
void
PriorityQueue<Key>::CASCADING_CUT(Vertex* y) {
	Vertex* z = y->parent;
	if (z) {
		if (y->mark) {
			CUT(y, z);
			CASCADING_CUT(z);
		}
		else
		{
			y->mark = true;
		}
	}
}


//instantiation of template class PriorityQueue

template <typename... Types> struct TypeList {};
typedef TypeList<int, double, bool, char, const char*, myTuple> MyTypeList;

template<typename T> struct SomethingDoer
{
	static int doSomething()
	{
		return 0;
	}
};
template<typename Head, typename... Tail>
struct SomethingDoer<TypeList<Head, Tail...>>
{
	typedef void (PriorityQueue<Head>::*MemFuncType)(Head);
	static int doSomething()
	{
		PriorityQueue<Head> myQueue;
		auto pointer = myQueue.insert(Head());
		myQueue.increaseKey(pointer, Head());
		myQueue.getMax();
		myQueue.extractMax();
		return SomethingDoer<TypeList<Tail...>>::doSomething();
	}
};
int a = SomethingDoer<MyTypeList>::doSomething();